[POJ 3415] Common Substrings

原题链接：http://poj.org/problem?id=3415
题目大意：给定两个字符串$A$和$B$，求两者长度至少为$k$的公共子串的数量。
数据范围：
多组测试数据
$1 \leq |A|,|B| \leq 10^5$
$1 \leq k \leq min(|A|,|B|)$
字符集只有字母

前面写过一个求公共子串长度的题POJ 2217这个题的处理方法其实也是同理，直接两者粘一起就行了。
由于说范围太大了，所以这个题大概的也就$O(N)$的复杂度。
对于$LCP$有一个重要的结论：对于两个位置$i$和$j$来说，如果有$rank[i] < rank[j]$，则$LCP(i,j)$就是$k \in [rank[i],rank[j] - 1]$之间的最小的$LCP[k]$。对于每一个位置$i$来说，如果他和下一位的$LCP$的长度至少为$k$的话，那么假设他是合法的，贡献就会增加$LCP - k + 1$，把其中$k$个看成$1$个，剩下的$LCP - k$个是额外对应进去的。对于实际的答案统计来说，还需要判断两边是否是来自$A$和$B$，所以如果这里直接全部把贡献统计进去会很混乱。所以要分成两种情况进行统计，这里定义一个$slove$函数，第一次只把是$SA[i]$是左半部分的加入贡献，第二次只把是右边的加入贡献。但是这种统计方法是直接把$k$长度之外的部分也统计进贡献的，假如说下一位的$LCP$增大了，前面的多余部分是没问题的，但是如果减小了，会导致贡献有误。

对特定的$(i,j)$的$LCP$来说他应该是整个区间的最小值，但是如果往后拓展的同时，发现有某一个$LCP$比前面都小，就说明：前面加进去的贡献是有多余的部分的，因为前面的$LCP$算出来的不并正确，不是真正的最小值。对于单个的$slove$函数来说，我们发现如果$LCP$满足递增的性质的话，贡献是可以一直累加的，但是显然情况不会有这么好，于是可以通过单调栈来维护一个单调上升的$LCP$集合。如果有违反单调性质的$LCP$，则在栈中删去的同时，还维护一个之前已经有过的$size$即在$A$里选了几个之前的位置，之后如果有影响的，要把这段全加进去去掉相应的贡献。

最后把贡献加进答案的时候要特别看一下，因为这里的$slove$是两个情况，所以最后加答案还要看下一位（就是$LCP$的定义里的下一位）是不是另外一边的，如果是才会把答案统计进去，否则没意义，因为不能自己和自己求公共子串。

代码：

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 2e5+7;
int lcp[N],sa[N],stk[N][2];
namespace SA
{
	int rank[N],tmp[N];
	int n,k;
	bool sa_cmp(int i,int j)
	{
		if(rank[i] != rank[j])	return rank[i] < rank[j];
		else
		{
			int ri = i + k <= n ? rank[i + k] : -1;
			int rj = j + k <= n ? rank[j + k] : -1;
			return ri < rj;
		}
	}
	void build_sa(string& s)
	{
		n = s.size();
		for(int i = 0;i <= n;++i)
		{
			sa[i] = i;
			rank[i] = i < n ? s[i] : -1;
		}
		for(k = 1;k <= n;k *= 2)
		{
			sort(sa,sa + 1 + n,sa_cmp);
			tmp[sa[0]] = 0;
			for(int i = 1;i <= n;++i)	tmp[sa[i]] = tmp[sa[i - 1]] + sa_cmp(sa[i - 1],sa[i]);
			for(int i = 0;i <= n;++i)	rank[i] = tmp[i];
		}
	}
	bool contain(string& s,string& T)
	{
		int l = 0,r = s.size();
		while(l < r)
		{
			int mid = l + r >> 1;
			if(s.compare(sa[mid],T.size(),T) < 0)	l = mid + 1;
			else r = mid;
		}
		return s.compare(sa[l],T.size(),T) == 0;
	}
	void build_lcp(string& s)
	{
		n = s.size();
		for(int i = 0;i <= n;++i)	rank[sa[i]] = i;
		
		int h = 0;
		lcp[0] = 0;
		for(int i = 0;i < n;++i)
		{
			int j = sa[rank[i] - 1];
			if(h > 0)	--h;
			for(;j + h < n && i + h < n;++h)
				if(s[j + h] != s[i + h])	
					break;
			lcp[rank[i] - 1] = h;
		}
	}
}
ll slove(string& s,int k,int left,bool is_sa)
{
	ll res = 0,tmp = 0;
	int n = s.size(),top = 0;
	for(int i = 0;i < n;++i)
	{
		if(lcp[i] < k)	top = 0,tmp = 0;
		else
		{
			int sz = 0;
			if((is_sa && sa[i] < left) || (!is_sa && sa[i] > left))
			{
				++sz;
				tmp += lcp[i] - k + 1;
			}
			while(top > 0 && lcp[i] <= stk[top - 1][0])
			{
				--top;
				tmp -= stk[top][1] * (stk[top][0] - lcp[i]);
				sz += stk[top][1];
			}
			if(sz)
			{
				stk[top][0] = lcp[i];
				stk[top][1] = sz;
				++top;
			}
			
			if((is_sa && sa[i + 1] > left) || (!is_sa && sa[i + 1] < left)) 
				res += tmp;
		}
	}
	return res;
}
int main()
{
	ios::sync_with_stdio();cin.tie(0);
	int k;
	while(cin >> k,k)
	{
		string a,b;cin >> a >> b;
		int n = a.size(),m = b.size();
		int L = n + m + 1;
		string s = a + '\0' + b;
		SA::build_sa(s);
		SA::build_lcp(s);
		cout << slove(s,k,n,1) + slove(s,k,n,0) << endl;
	}
    return 0;
}